# 方法一
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = []
        ret = []
        # 生成空三角
        for i in range(rowIndex + 1):
            ret = []
            for j in range(i + 1):
                ret.append(None)
            ans.append(ret)
        # 赋值
        for i in range(len(ans)):
            for j in range(len(ans[i])):
                if j == 0 or j == len(ans[i]) - 1:
                    ans[i][j] = 1
                else:
                    ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
                if i == (rowIndex + 1):
                    ret.append(ans[i][j])
        return ret

# 空间优化一
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = []
        # 生成空三角
        for i in range(rowIndex + 1):
            ret = []
            for j in range(i + 1):
                ret.append(None)
            ans.append(ret)
        # 赋值
        for i in range(len(ans)):
            for j in range(len(ans[i])):
                if j == 0 or j == len(ans[i]) - 1:
                    ans[i][j] = 1
                else:
                    ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
        return ans[-1]


# 空间优化二
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        elif rowIndex == 1:
            return [1, 1]
        temp = [1, 1]
        ans = [None] * (rowIndex + 1)

        # 赋值
        for i in range(2, len(ans)):
            for j in range(len(temp) + 1):
                if j == 0 or j == len(temp):
                    ans[j] = 1
                else:
                    ans[j] = temp[j - 1] + temp[j]
            
            # 更新存储的暂时数组
            for j in range(len(temp) + 1):
                if j == len(temp):
                    temp.append(1)
                else:
                    temp[j] = ans[j]
        return ans

# 线性递推
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(1, rowIndex + 1):
            row[i] = row[i - 1] * (rowIndex - i + 1) // i
        return row